import com.sun.source.tree.Tree;

import java.util.*;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;//存储左孩子的引用
        public TreeNode right;//存储右孩子的引用

        public TreeNode(char val){
            this.val=val;
        }
    }
//    public TreeNode creatTree(){
//        TreeNode A=new TreeNode('A');
//        TreeNode B=new TreeNode('B');
//        TreeNode C=new TreeNode('C');
//        TreeNode D=new TreeNode('D');
//        TreeNode E=new TreeNode('E');
//        TreeNode F=new TreeNode('F');
//        TreeNode G=new TreeNode('G');
//        TreeNode H=new TreeNode('H');
//        A.left=B;
//        A.right=C;
//        B.left=D;
//        B.right=E;
//        C.left=F;
//        C.right=G;
//        E.right=H;
//        return A;
//    }


//二叉树的构建及其遍历
//给你一个前序遍历的字符串根据这个字符串来创建一个二叉树
    public   int i=0;
    public  TreeNode creatTree(String str){

        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=creatTree(str);
            root.right=creatTree(str);
        }else {
            i++;
        }
        return root;
    }

    //前序遍历
    public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+"  ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //非递归的前序遍历
    public void perorderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+"  ");
        inOrder(root.right);
    }
    public void inorderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(cur.val+" ");
            cur=top.right;
        }
    }
    //后续遍历
    public  void postOrder(TreeNode root){
         if(root==null){
             return;
         }
         postOrder(root.left);
         postOrder(root.right);
        System.out.print(root.val+"  ");
    }
    //后续非递归遍历
    public void postOrderNor(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if(top.right==null||top.right==prev){
                System.out.print(top.val+" ");
                stack.pop();
                prev=top;
            }else {
                cur=top.right;
            }
        }
    }





    //二叉树的层序遍历   运用队列来进行实现
    public void levelOrder(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode  cur=queue.poll();
            System.out.print(cur.val);
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }
    //二叉树的层序遍历， 运用二维顺序表的知识来进行实现，把每一层放到相应的二维数组表中
    public List<List<Character>>levelOrder2(TreeNode root){
        List<List<Character>> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size= queue.size();
            List<Character> list=new ArrayList<>();
            while(size!=0){
                TreeNode  cur=queue.poll();
                //System.out.print(cur.val);
                list.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
           ret.add(list);
        }
        return ret;
    }


    //判断一棵树是不是完全二叉树
    public boolean iscompleteBinaryTree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode  cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while(!queue.isEmpty()){
            TreeNode peek=queue.peek();
            if(peek!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }


    //二叉树的最近公共祖先：给定一个二叉树，找到该树中两个指定结点的最近公共祖先**************************************
    //p或者q就是root那么root就是公共祖先
    //左边不为空&&右边不为空
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return null;
        }
        if(root==p&&root==q){
            return root;
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if(leftTree!=null&&rightTree!=null){
            return root;
        }else if(leftTree!=null){
            return  leftTree;
        }else {
            return rightTree;
        }
    }

    //解法二  用两个链表的求交点的思想来实现
    //先创建一个栈，在栈中存放根节点到p的最短路径；先遍历一边树，如果是最短路径中的一部分就存放到栈中，否则就会弹出
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root==null){
            return false;
        }
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean ret=getPath(root.left,node,stack);
        if (ret) {
            return true;
        }
        ret=getPath(root.right,node,stack);
        if(ret){
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return null;
        }
         Stack<TreeNode>stackP=new Stack<>();
         Stack<TreeNode>stackQ=new Stack<>();
         getPath(root,p,stackP);
         getPath(root,q,stackQ);
         int sizeP=stackP.size();
         int sizeQ=stackQ.size();
         if(sizeP>sizeQ){
             int size=sizeP-sizeQ;
             while(size!=0){
                 stackP.pop();
                 size--;
             }
         }else {
             int size=sizeQ-sizeP;
             while(size!=0){
                 stackQ.pop();
                 size--;
             }
         }
         while(!stackP.isEmpty()&&!stackQ.isEmpty()){
             if(stackP.peek()==stackQ.peek()){
                 return stackP.peek();
             }else {
                 stackP.pop();
                 stackQ.pop();
             }
         }
         return  null;

    }



    //把前序遍历的数据保存下来,保存到一个列表中***********
    public List<Character> preorderTraversal(TreeNode root){
        List<Character> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        list.add(root.val);
        //System.out.print(root.val+"  ");
        List<Character> leftTree= preorderTraversal(root.left);
        list.addAll(leftTree);
        List<Character> rightTree=preorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
    //获取树中结点的个数
    //1遍历二叉树，只要root不为空++
    //整棵树有多少结点就是=左子树的结点+右子树的结点+1
    public static int nodesize=0;
    public int size1(TreeNode root){
        if(root==null){
            return 0;
        }
        nodesize++;
        size1(root.left);
        size1(root.right);
        return nodesize;
    }
    public int size2(TreeNode root){
        if(root==null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }


    //获取叶子结点的个数  root的左边和右边都是空的时候就是叶子  整棵树的叶子结点就是左边树叶子结点加右边树叶子结点
    public int getleafNodeCount(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return  getleafNodeCount(root.left)+
                 getleafNodeCount(root.right);
    }
    //遍历的思路
    public int getleafsize=0;
    public  void getleafNodeCount2(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left!=null&&root.left==null){
            getleafsize++;
        }
        getleafNodeCount(root.left);
        getleafNodeCount(root.right);
    }

    //求第k层结点的个数
    public  int getKlevelNodeCount(TreeNode root,int k){
       if(root==null){
           return 0;
        }
       if(k==1){
           return 1;
       }
       return getKlevelNodeCount(root.left,k-1)+
               getKlevelNodeCount(root.right,k-1);
    }

    //获取二叉树的高度
    //左树的高度和右侧树的高度的最大值+1
    //分别求左数和右树的高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;

    }

    //检测你的val是否存在
    public TreeNode findVal(TreeNode root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode leftT=findVal(root.left,val);
        if(leftT!=null){
            return leftT;
        }
        TreeNode rightT=findVal(root.right,val);
        if(rightT!=null){
            return rightT;
        }
        return null;
    }

    //检查两棵树是不是相同的树
    //判断结构是否一样
    //如果一样，则判断值是否一样
    //如果值一样，则开始判断当前节点的左子树是否一样&&右子树是否一样
    public boolean isSameTree(TreeNode p,TreeNode q){
        //先判断结构一样不一样
        if(p!=null&&q==null||p==null&&q!=null){
            return false;
        }
        //上述if语句，如果没有执行，意味着两个引用同时为空或同时不为空
        if(p==null&&q==null){
            return true;
        }
        //都不为空判断值一样不
        if(p.val!=q.val){
            return false;
        }
        //都不为空且值一样
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.left);
    }


    //判断某一个树是否是另一棵树的子树
    //思路：1当前子树的根节点是否一样？
    //判断子树是不是当前root的左子树一样？
    //判断子树是不是房前root的右子树一样？
    public boolean isSubTree(TreeNode root,TreeNode subRoot){
        if(root==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
             return true;
        }
       if(isSubTree(root.left,subRoot)) {
           return true;
       }
        if(isSubTree(root.right,subRoot) ) {
            return true;
        }
        return false;
    }



    //翻转二叉树 左子树变右子树  右子树变左子树
    public TreeNode invertTree(TreeNode root){
        if(root==null){
            return null;
        }
        if(root.left==null&&root.right==null){
            return root;
        }
        TreeNode tmp= root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
       return root;
    }


    //对称二叉树 给你一个二叉树的根节点root，检查它是否是轴对称的
    //要判断整棵树是轴对称的我们需要判断：root的左子树和右子树是轴对称的。如何判断左子树和右子树是轴对称的呢？
    public boolean isSymmetric(TreeNode root){
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree!=null&&rightTree==null||leftTree==null&&rightTree!=null){
            return false;
        }
        if(leftTree==null&&rightTree==null){
            return true;
        }
        if(leftTree.val!= rightTree.val){
            return false;
        }
       return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
    }


    //判断一棵树是否是平衡二叉树
    //什么是平衡二叉树呢？左子树和右子树相差的的深度不能超过1。 如果一棵树是平衡二叉树，那么它的每棵子树都是平衡二叉树
    //思路遍历当前这棵树的每个结点，求每个节点的左数和右树的高度，如果发现高度大于2，则返回false
    //时间复杂度on^2
    public boolean isBalanced(TreeNode root){
        if(root==null){
            return true;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.abs(leftHeight-rightHeight)<2&&isBalanced(root.left)&&isBalanced(root.right);
    }
    //解法2 时间复杂度为on
    public  boolean isBalance2(TreeNode root){
        if(root==null){
            return true;
        }
        return geTHeight2(root)>=0;
    }
    public  int geTHeight2(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=geTHeight2(root.left);
        if(leftHeight<0){
            return -1;
        }
        int rightHeight=geTHeight2(root.right);
        if(rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            return -1;
        }
    }
    //二叉搜索树：每一个结点的左子树都比根节点小，右子树都比根节点大***************************************************重新看
    //把二叉搜索树换成一个排好序的双向链表  ：如果你对一个二叉搜索树进行中序遍历那么它的中序遍历就是有序的
    //解答二叉树第二节2.38
    TreeNode prev=null;
    public void ConverChild(TreeNode root){
        if(root==null){
            return;
        }
        ConverChild(root.left);
        root.left=prev;
        if(prev!=null){
            prev.right=root;
        }
        prev=root;
        ConverChild(root.right);
    }
    public TreeNode Conver(TreeNode prootOfTree){
        if(prootOfTree!=null){
            return null;
        }
        ConverChild(prootOfTree);
        TreeNode head=prootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;
    }

//给你二叉树的结点root，请你采用前序遍历的方式，将二叉树转化成一个由括号和整数组成的字符串，返回构造出字符串
    public String tree2str(TreeNode root){
        if(root==null){
            return null;
        }
        StringBuffer stringBuffer=new StringBuffer();
        tree2strchild(root,stringBuffer);
        return stringBuffer.toString();
    }
    public void tree2strchild(TreeNode t,StringBuffer stringBuffer){
        if(t==null){
            return;
        }
        stringBuffer.append(t.val);
        if(t.left!=null){
            stringBuffer.append("(");
            tree2strchild(t.left,stringBuffer);
            stringBuffer.append(")");
        }else {
            if(t.right==null){
                return;
            }else {
                stringBuffer.append(")");
            }
        }
        if(t.right!=null){
            stringBuffer.append("(");
            tree2strchild(t.right,stringBuffer);
            stringBuffer.append(")");
        }else{
            return;
        }
    }






}
